package 文库检索;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Demo {
    public static boolean search_main(Pair<String,Integer>[] arr,int beg,int end,String find){
        //首先先用二分找一下这个Hash存在否
        int start = binary_search_hash(arr, beg, end, find.hashCode());
        if(start==-1)return false;
        //Hash存在 再查相同Hash的区域
        return search_string(arr,search_equalhash_section(arr,start,end),find);
    }

    public static boolean search_string(Pair<String,Integer>[] arr,Pair<Integer,Integer> section,String str){
        for(int i = section.first;i<=section.second;++i){
            if(str.equals(arr[i].first))return true;
        }
        return false;
    }
    public static Pair<Integer,Integer> search_equalhash_section(Pair<String,Integer>[] arr,int start,int last){
        int left=start,right=start;
        for(;left>0 & arr[left].second==arr[start].second;--left);
        for(;right<last & arr[right].second==arr[start].second;++right);
        return new Pair<>(left,right);
    }
    public static int binary_search_hash(Pair<String,Integer>[] arr,int beg,int end,int hashcode){
        if (beg > end)return -1;
        int half = (beg+end)/2;
        if(arr[half].second == hashcode)return half;
        if(arr[half].second > hashcode)return binary_search_hash(arr,beg,half-1,hashcode);
        return binary_search_hash(arr,half+1,end,hashcode);
    }

    public static void quick_sort(Pair<String,Integer>[] arr,int l,int r){//--------------快排
        if(l < r){
            int left = l,right = r;
            Pair<String,Integer> temp = arr[l];
            while (left != right) {   //从左右两边交替扫描，直到left = right
                while (left < right && arr[right].second >= temp.second)right--;
                arr[left] = arr[right];
                while (left < right && arr[left].second <= temp.second)left++;
                arr[right] = arr[left];
            }
            arr[right] = temp;
            quick_sort(arr, l, left - 1);
            quick_sort(arr, right + 1, r);
        }
    }

    public static void main(String[] args) throws IOException {
        Pair<String,Integer>[] arr = new Pair[108000];
        BufferedReader bfr = new BufferedReader(new FileReader("百度分词词库.txt"));//百度分词词库.txt
        int index = 0;
        String s = null;
        while((s= bfr.readLine())!=null){
            arr[index++] = Pair.make_pair(s,s.hashCode());
        }
        bfr.close();

//        quick_sort(arr,0,index-1);//!!!!!!!!! 注 意 这 里 快排因为数据过大 而导致递归过深
        Arrays.sort(arr,(o1, o2) -> (o1==null || o2==null)?0:(o1.second < o2.second ?  -1:1));

        Scanner sc = new Scanner(System.in);
        System.out.println("加载成功");
        while(!(s = sc.next()).equals("886")){
            System.out.println(search_main(arr,0,index-1,s) ? "存在" : "不存在");
        }
    }
}
